﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0018_LongestCommonPrefix
    {
        // 最长公共前缀

        // 编写一个函数来查找字符串数组中的最长公共前缀。
        // 如果不存在公共前缀，返回空字符串 ""。

        // 提示：
        //   1 <= strs.length <= 200
        //   0 <= strs[i].length <= 200
        //   strs[i] 仅由小写英文字母组成

        public void Test()
        {
            string[] strs = new string[] { "dog", "racecar", "car" };
            Console.WriteLine(LongestCommonPrefix(strs));
            Console.Read();
        }

        public string LongestCommonPrefix(string[] strs)
        {
            int i = 0;
            string result = "";
            while (true)
            {
                string temp = string.Empty;
                for (int j = 0; j < strs.Length; j++)
                {
                    if (i == strs[j].Length)
                        return result;
                    if (j == 0)
                        temp = strs[0][i].ToString();
                    else if (strs[j][i].ToString() != temp)
                        return result;
                }
                result += temp;
                i++;
            }
        }

        // 优化解
        public string LongestCommonPrefix1(string[] strs)
        {
            if (strs == null || strs.Length == 0)
                return "";
            string pre = strs[0];
            int i = 1;
            while (i < strs.Length)
            {
                while (strs[i].IndexOf(pre) != 0)
                    pre = pre[0..^1];
                i++;
            }
            return pre;
        }
    }
}
